package basic.study.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @ClassName Mid22
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/18 9:32
 * @Version 1.0
 */
public class Mid22 {
    /**
     * 深度优先1
     */
    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            if (n == 0) {
                return res;
            }
            //深度优先遍历
            dfs("",n,n,res);
            return res;
        }

        private void dfs(String s, int left, int right, List<String> res) {
            if (left == 0 && right == 0) {
                res.add(s);
                return;
            }
            //左括号可以使用个数
            if (left > right) {
                return;
            }
            if (left>0) {
                dfs(s+"(", left-1, right, res);
            }
            if (right>0) {
                dfs(s + ")", left, right-1, res );
            }
        }
    }
    /**
     * 深度优先2
     */
    class Solution1 {
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            if (n == 0) {
                return res;
            }
            dfs("", 0, 0, n, res);
            return res;
        }

        private void dfs(String s, int left, int right, int n, List<String> res) {
            if (left == n && right == n) {
                res.add(s);
                return;
            }
            if (right > left) {
                return;
            }
            if (left < n) {
                dfs(s + "(", left+1, right, n, res);
            }
            if (right < n) {
                dfs(s + ")", left, right+1, n, res);
            }
        }
    }
    /**
     * 广度优先
     */
    class Solution2 {
        class Node {
            int left;
            int right;
            String res;
            public Node(String str, int left, int right) {
                res = str;
                left = left;
                right = right;
            }
        }
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            if (n == 0) {
                return res;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(new Node("", n, n));

            while (!queue.isEmpty()) {
                Node node = queue.poll();
                if (node.left == 0 && node.right == 0) {
                    res.add(node.res);
                }
                if (node.left > 0) {
                    queue.offer(new Node(node.res + "(", node.left -1, node.right));
                }
                if (node.right > 0 && node.left < node.right) {
                    queue.offer(new Node(node.res + ")", node.left, node.right-1));
                }
            }
            return res;
        }
    }
    /**
     * 动态规划
     */
    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        List<List<String>> dp = new ArrayList<>();
        List<String> dp0 = new ArrayList<>();
        dp0.add("");
        dp.add(dp0);

        for (int i = 1; i <= n; i++) {
            List<String> cur = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                List<String> str1 = dp.get(j);
                List<String> str2 = dp.get(i - j - 1);
                for (String s1: str1) {
                    for (String s2: str2) {
                        cur.add("(" + s1 + ")" + s2);
                    }
                }
            }
            dp.add(cur);
        }
        return dp.get(n);
    }

}
